﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.CountPrimes
{
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine(CountPrimes2(10000));
            Console.ReadKey();
        }

        /// <summary>
        /// 埃拉托斯特尼筛法
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int CountPrimes2(int n)
        {
            bool[] ars = new bool[n];
            int count = 0;
            for (int i = 2; i < n; i++)
            {
                if (ars[i])
                    continue;
                count++;
                for (int k = i; k < n; k += i)
                {
                    ars[k] = true;
                }
            }
            return count;
        }

        /// <summary>
        /// 试除法（有问题）
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int CountPrimes(int n)
        {
            if (n >= 4)
            {
                int count = 2;
                for (int i = 4; i < n; i++)
                {
                    if (i % 2 != 0 && i % 3 != 0)
                    {
                        count++;
                    }
                }
                return count;
            }
            else
            {
                if (n == 3)
                {
                    return 2;
                }
                else if (n == 2)
                {
                    return 1;
                }
                else
                {
                    return 0;

                }
            }
        }
    }
}
